У яких життєвих задачах потрібно сортувати набори об'єктів?

На минулих уроках ми виконували різні дії зі списками. досить часто в програмуванні працювати зі списками ефективніше, коли вони відсортовані, тобто їхні елементи впорядковані за зростанням чи спаданням. для сортування списків у більшості мов програмування, зокрема в Python, є стандартні (бібліотечні) методи, з якими ми познайомимося на цьому уроці. використовувати такі методи просто, однак не дуже цікаво. Значно цікавіше розібратися «зсередини» за якими алгоритмами ці методи можуть працювати!

І цим ми теж займемося сьогодні, розглянувши одним з найвідомі-ших і найпростіших алгоритмів сортування списків.

Завдання № 1

дізнайся з рубрики «Запитання-відповіді» про метод sort().

Що буде виведено в результаті виконання команди print(a.sort()), якщо спочатку цей список був таким: 4, -3, 12, 0, 5?

Як будуть розташовані елементи списку а після виконання команди a.sort(reverse=True), якщо спочатку цей список був таким: 4, -3, 12, 0, 5?

Завдання № 2

Створи за зразком інтерфейс для програми сортування списку.

У програмі має бути: текстове поле Ent1; кнопка Btn з написом «Сортувати»; поле списку Lboxl;

2 написи, «вхідний список:» і «Результат:».

Доповни код, за допомогою якого можна створити список дійсних чисел а з розташованих у текстовому полі Ent даних, записаних через пробіл.

Завдання № 4

Програма має працювати так: користувач вводить у текстове поле список чисел через пробіл, натискає кнопку — і цей список має відобразитися в полі списку у відсортованому вигляді.

Заповни пропуск в коді обробника події натискання кнопки «Сортувати» та реалізуй його в програмному середовищі. Не забудь в конструкторі кнопки «Сортувати» присвоїти параметру command назву методу btn_ click.

Завдання № 5

Ми познайомилися зі стандартним методом sort(), а тепер розберемся, як він працює «зсередини», який алгоритм у ньому може бути реалізовано. Існують десятки алгоритмів сортування, більш чи менш швидких. Одним із найпростіших є метод «бульбашок».

Принцип цього методу полягає у попарному порівнянні елементів та обміну їх місцями, доки більші елементи не перестануть «спливати» до кінця списку, а дрібніші залишатимуться «знизу».

Нехай у нас є 3 позиції (змінні) a, b, c. Нам потрібно розмістити на цих позиціях три бульбашки в порядку зростання їхнього розміру. Припустимо, що спочатку вони розташовувалися в протилежному порядку:

Крок 1.

Порівняємо дві перші бульбашки, а і b. Нам потрібно, щоб менша бульбашка була лівіше. Оскільки a>b, міняємо бульбашки місцями.

Головний принцип: менша бульбашка має бути лівіше.

У «бульбашковому» методі спочатку порівнюються 1-й і 2-й елементи, потім 2-й і 3-й, потім — 3-й і 4-й тощо. У результаті найбільший елемент опиниться справа.

доповни словесний алгоритм наступних кроків.

Крок 2.

Порівнюємо бульбашки_і_. Якщо_, то_.

Крок 3.

Повторюємо алгоритм спочатку і порівнюємо бульбашки_

і_. Якщо_, то_.

Ми отримали бажаний результат!

Увага!

Коли найбільша бульбашка спливла справа, повторюємо весь процес, але цю найбільшу бульбашку вже не чіпаємо.

Завдання № 6

Ознайомся із застосування методу бульбашок до списку з 10 елементів, переглянувши відео

Проаналізуй відео і опиши процес «бульбаш-кового» сортування за зростанням.

Під час перегляду відео став його на паузу і відповідай на запитання письмово в зошиті: Яким був початковий список?

Які елементи порівнюються? (Занотуй кожне порівняння).

доки повторюється процес попарного порівняння елементів?

Що трапляється, коли всі пари елементів порівняно?

http://bit.do/fSPWC

Заповни пропуски у тексті, що описує алгоритм сортування списку за зростанням методом бульбашок.

1. Порівнюється черговий елемент списку з_.

2. Якщо_елемент_, то_.

3. Після порівняння всіх пар_елемент переміщується

_списку.

4. Процес повторюється від початку списку до__

елемента включно.

Завдання № 8

виконай покроково алгоритм сортування списку A=[9,5,4,8,3] методом «бульбашок» і занотуй послідовність змін вмісту списку за прикладом:

Завдання № 9

Користуючись рубрикою «Запитання-відповіді», вибери команду, за допомогою якої перший та останній елементи списку [2,6,7,4,3] поміняються місцями

Завдання № 10

1) Заповни пропуски в коді, що сортує список а методом «бульбашок». і-й елемент списку має порівнюватися з i+1-м і якщо і-й елемент більший, то елементи мінятимуться місцями.

2) Можна зауважити, що в коді лічильники j (зовнішнього) та і (внутрішнього) циклів змінюються в діапазонах, що залежать від довжини заданого списку. В даному випадку список містить 5 елементів. Які зміни в коді необхідно зробити для того, щоб програма діяла для списків із будь-якою кількістю елементів?

3) Чому в команді range у внутрішньому циклі записано формулу 5-j? Поясни словами, що вона означає.

Завдання № 11

Реалізуй сортування списку методом бульбашок у Python, визначивши вміст списку за допомогою оператора присвоювання. виводь список командою print його після кожної ітерації зовнішнього циклу, який відповідає за один прохід по всьому списку.

Завдання № 12

1) Додай до інтерфейсу програми з Завдання №3 ще одну кнопку для реалізації сортування методом бульбашок та ще одне поле списку для виведення результату і порівняння.

2) Скопіюй код обробника події натискання кнопки «Сортувати» та заміни його кодом із завдання №10. Модифікуй цей код так, щоб він сортував методом бульбашок стільки елементів, скільки буде у списку. Забезпеч виконання цього методу по натисканні кнопки «Сортувати бульбашкою». Порівняй сортування двома способами на кількох прикладах — результати мають збігатися.

ЗАПИТАННЯ-ВІДПОВІДІ

Що таке сортування списку?

Сортування списку — це розміщення його елементів у порядку їх зростання (від меншого до більшого) чи спадання (від більшого до меншого).

даний список	Список впорядковано за зростанням	Список впорядковано за спаданням
3	1	7
1	2	5
7	3	3
5	5	2
2	7	1

Сортування та впорядкування — це одне те саме.

Для чого призначений метод sort()?

Метод sort застосовується до списку (тобто його назву записують через крапку після імені списку). Якщо цей метод викликано без параметрів, він впорядковує елементи списку у порядку зростання. для сортування списку в порядку спадання використовують параметр reverse (англ. «зворотний») зі значенням True. Наприклад, у результаті виконанні фрагменту програми

буде одержано результат

як поміняти місцями значення змінних a та b?

Значення змінних а та b можна поміняти місцями, використовуючи третю змінну, наприклад с:

Цей спосіб ви мали вивчати в 7 класі. Але у Python існує значно простіший спосіб обміну значеннями змінних: a, b = b, а Обидва способи є рівносильними, тобто завжди дають однаковий результат.

У чому полягає бульбашковий метод сортування списку?

Метод передбачає кілька проходів списком. А саме, кількість проходів дорівнює довжині списку, зменшеній на 1. На кожному проході послідовно порівнюють усі пари сусідніх елементів у ще не відсортованій частині списку. Якщо список сортують за зростанням і лівіший елемент більший за правіший, то ці елементи міняють місцями.

У результаті першого проходу більший елемент «спливе» в кінці списку справа. На другому проході його вже не треба чіпати, а на передостанній справа позиції «спливе» другий за величиною елемент списку. Таким чином, відсортована частина списку складатиметься з двох елементів і буде розташована з його правого краю. З кожним проходом ця відсортована частина збільшуватиметься на один елемент, аж поки не охопить увесь список, динамічну візуалізацію методу можна розглянути за посиланням:

Також за посиланням можна спостерігати за сортуванням методом бульбашки списку, введеним власноруч через пропуск: bit.do/fSgh6 Проаналізуємо метод бульбашок на прикладі сортування списку а=[6,5,7,3,1] за зростанням. Червоним овалом позначено порівняння сусідніх елементів та, якщо лівіший є більшим, то їх обмін місцями.

bit.do/fSghT

Розглянутий алгоритм можна реалізувати за допомогою вкладених циклів:

у зовнішньому циклі рахуватиметься кількість проходів; у внутрішньому циклі порівнюватимуться сусідні елементи. Призначення лічильників зовнішнього та внутрішнього циклу буде таким: номер проходу — зовнішній цикл; індекс елемента, що порівнюється з наступним, — внутрішній цикл.

Діапазон зміни лічильника j зовнішнього циклу — від 1 до len(a)-включно, а внутрішнього циклу — від 0 до len(a)-j.

ПЕРЕВІР СЕБЕ

1. Скільки порівнянь елементів буде виконано під час сортування списку [4,1,2,3] за зростанням бульбашковим методом? А скільки обмінів елементів місцями?

2. Є певний список х. Проаналізуй наведений нижче фрагмент програми. Вкажи, яким буде індекс елементу, що матиме значення у після виконання зображеного коду.

3. Скільки порівнянь елементів потрібно зробити під час сортування методом «бульбашок» n-елементного списку?

4. Доповни програму, створену в завданні 12, ще двома полями списку. У першому має відображатися введений користувачем список, відсортований за спаданням бібліотечним методом, а в другому — за спаданням методом бульбашок.

5. Метод сортування списку «бульбашками» є одним із найпростіших. Як ти думаєш, чи є він найшвидшим? Чи можеш запропонувати інший метод, який працюватиме швидше?

 

 

Це матеріал з підручника Інформатика 9 клас Коршунова 2022